//H+
//	Implementation of a LIFO stack or FIFO queue via a
//	doubly-linked list.
//
/*	$Log:	Queue.m,v $
Revision 1.2  94/05/15  18:56:05  ediger
speedup -free method.  keep from honking internals up on -pop and -first
methods.

Revision 1.1  94/05/14  17:44:25  ediger
Initial revision

*/

//H-
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <libc.h>

#include <Queue.h>

#define CHECK_CONTRACT

#ifdef CHECK_CONTRACT
	#define REQUIRE(c) if(![self c]) \
        [self error:"%s precondition check failed", sel_getName(_cmd)]
	#define ENSURE(c) if(![self c]) \
        [self error:"%s postcondition check failed", sel_getName(_cmd)]
#else
    #define REQUIRE(c)
    #define ENSURE(c)
#endif


@implementation Queue: Object

static char RCSQueueIdent[] = "$Id";

#ifdef CHECK_CONTRACT
//M+ -(BOOL)listOK
//	PURPOSE:
//		Make sure that head and tail dummy nodes are OK.
//		Used as pre- and post-condition for most methods when
//		CHECK_CONTRACT is #defined
//	EDITORIAL:
//		Could walk the entire list forward and back to see
//		if all the links are correct, but it doesn't.
//M-
-(BOOL)listOK
{
	return
		   (head != NULL) && (tail != NULL)
		&& (head->next != NULL)
		&& (tail->prev != NULL)
		&& (head->next->prev == head)
		&& (tail->prev->next == tail)
	;
}
#endif

//M+ - init
//	PURPOSE:
//		initialize internals of an object.  In this implementation, that
//		means setting up dummy head and tail nodes of doubly-linked list.
//M-
- init
{
	head = (struct qs_internal_node *)malloc(sizeof(struct qs_internal_node));
	assert(head != NULL);
	tail = (struct qs_internal_node *)malloc(sizeof(struct qs_internal_node));
	assert(tail != NULL);

	head->next = tail;
	head->prev = head;
	head->ptr  = NULL;

	tail->next = tail;
	tail->prev = head;
	tail->ptr  = NULL;

	ENSURE(listOK);

	return self;
}

//M+ -push:(void *)p
//	PURPOSE:
//		push something onto the stack, or end of queue.
//M-
-push:(void *)p
{
	struct qs_internal_node *new;

	REQUIRE(listOK);

	new = (struct qs_internal_node *)malloc(sizeof *new);
	assert(new != NULL);

	new->ptr = p;
	new->prev = tail->prev;
	new->next = tail;

	tail->prev = new;

	new->prev->next = new;

	ENSURE(listOK);

	return self;
}

//M+ -(void *)first
//	PURPOSE:
//		Retrieve the first thing that was pushed onto queue.
//		This is the method that makes object a FIFO.
//	RETURNS:
//		pointer to item stored.  If NULL was stored it will return NULL,
//		but it will also return NULL if queue is empty.
//	NOTE:
//		Should deallocate memory used internally by the object.
//M-
-(void *)first
{
	void *ret = NULL;

	REQUIRE(listOK);

	if (head->next != tail)
	{	// object has something in it.

		struct qs_internal_node *tmp = head->next;

		head->next = tmp->next;
		head->next->prev = head;

		ret = tmp->ptr;

		free(tmp);
	}

	ENSURE(listOK);

	return ret;
}

//M+ -(void *)pop
//	PURPOSE:
//		Retrieve last thing that was pushed onto stack.
//		Method used to make object into a LIFO.
//	RETURNS:
//		pointer to item stored.  If NULL was stored it will return NULL,
//		but it will also return NULL if stack is empty.
//
//	NOTE:
//		Should deallocate memory used internally by the object.
//M-
-(void *)pop
{
	void *ret = NULL;

	REQUIRE(listOK);

	if (tail->prev != head)
	{	// object has something in it.

		struct qs_internal_node *tmp = tail->prev;

		tail->prev = tmp->prev;
		tail->prev->next = tail;

		ret = tmp->ptr;

		free(tmp);
	}

	ENSURE(listOK);

	return ret;
}

//M+ -(void *)tail
//	PURPOSE:
//		Peek at whatever is at tail of stack.
//		This is what was just "pushed" on stack.
//M-
-(void *)tail
{
	REQUIRE(listOK);
	return tail->prev->ptr;
}

//M+ -(void *)head
//	PURPOSE:
//		Peek at whatever is at head of stack.
//		This is what is "first" on queue.
//M-
-(void *)head
{
	REQUIRE(listOK);
	return head->next->ptr;
}

//M+ -(BOOL)empty
//	PURPOSE:
//		Determine if stack/queue has anything in it
//M-
-(BOOL)isEmpty
{
	REQUIRE(listOK);
	return (head->next == tail);
}

//M+ - free
//	PURPOSE:
//		Deallocate memory used by the object.
//	NOTES:
//		Doesn't deallocate memory that is contained by the object's
//		implementation.  Only deallocates memory used by the implementation.
//M-
- free
{
	REQUIRE(listOK);

	// free the list in implementation independant way
	//while(![self empty])
	//	[self pop];

	// free the list in way that depends on doubly-linked lists
	// speed up the process, I hope.
	while (head->next != tail)
	{
		struct qs_internal_node *tmp = head->next->next;
		free(head->next);
		head->next = tmp;
	}

	free(head);
	free(tail);

	[super free];

	return self;
}

@end
